Field of the Invention
The present invention relates to systems and methods for the storage, computation, reliable communication and the ordering of events in systems that operate across geographically and/or locally distributed computer systems. More particularly, the present invention relates to entangled links to establish and maintain bipartite temporal intimacy between computers. Still more specifically the present invention relates to entangled transactions and their composition over entangled trees for managing exchanged and conserved quantities, awareness of time, and recovery from failures in a distributed computing systems.
Description of Related Art
Distributed Computing. Conventional transactions use two-phase commit or consensus protocols to achieve their ACID (Atomic, Consistent, Indivisible, and Durable) properties. Shared objects in application memory are manipulated by algorithms which enforce the linearizability abstraction. Unfortunately, as attractive as this abstraction is in theory, there is an enormous amount of mechanism (application code, libraries, operating system, kernel, driver, I/O device) before this ‘atomic’ abstraction can be translated into bit and packet activity on the connection (wires or fiber) between computers.
Conventional transactions based on two-phase commit or Paxos (or similar consensus algorithms) in the App layer are complex, slow, brittle, and don't survive disasters. A new mechanism is needed to provide a simpler and more fundamental way to implement transactions that are faster and more robust.
Thus, there is need for a new way of organizing the design of hardware and software to address the performance, reliability and complexity challenges of conventional transactions, and mechanisms to manage the ordering of events.
Conventional networks incorporate addressable (port) endpoints. An example being nodes in a network with Ethernet or IP addresses. This “endpoint addressing” abstracts away latency, failures and the physical network topology, and presents only a shared or aggregated bandwidth channel. This was useful in the past because the original purpose of the internet protocols was to share resources (such as printers), not data. Current cloud computer architectures are based on the TCP/IP model with those same endpoint addresses, however, their communication and addressability needs are greatly expanded beyond the original endpoint (port) addressing model of early computers connected to the internet.
Cluster Computing.
Servers in conventional clusters use multicast or unicast to broadcast regular server heartbeat messages to other members of the cluster. Each heartbeat message uniquely identifies the server that sends the message. Servers broadcast their heartbeat messages at regular intervals of (for example) 10 seconds. In turn, each server in a cluster monitors the multicast or unicast address to ensure that all peer servers' heartbeat messages are being sent. If a server monitoring the multicast or unicast address misses three heartbeats from a peer server (i.e., if it does not receive a heartbeat from the server for 30 seconds or longer), the monitoring server marks the peer server as “failed.” It then updates its local status, if necessary, to retract the services that were hosted on the failed server.
Several mechanisms have been proposed to manage the heartbeat between computers in a cluster or distributed computing environment. Examples include ORACLE, VERITAS Cluster Server, Hadoop and IBM Scale Out NAS.
Some prior art software uses an internal peer-to-peer global cluster heartbeat mechanism to recover from multiple disk, node, and connectivity failures. The server software uses a scalable, point-to-point heartbeat architecture to efficiently detect failures without flooding the server farm's network with heartbeat packets. Heartbeat failures automatically trigger a multicast discovery protocol to automatically determine the set of surviving servers. This is followed by “self-healing” recovery, which restores access to grid data and dynamically rebalances the storage load across the grid. The prior art uses heartbeat channels to detect server and networking outages.
They define a heartbeat as: a software method used to determine whether a network outage has occurred or a host has failed. Pairs of hosts periodically exchange small messages, and uninterrupted reception of these messages indicates that the hosts are functioning and able to communicate. Heartbeat exchanges are used to efficiently monitor the health of a server farm, and the default heartbeat interval is frequently one or more seconds.
Other examples use the cluster interconnect for network communications between cluster systems. Each system runs as an independent unit and shares information at the cluster level. On each system a High Availability Daemon (HAD), which is the decision logic for the cluster, maintains a view of the cluster configuration. This daemon operates as a replicated state machine, which means all systems in the cluster have a synchronized state of the cluster configuration. This is accomplished by the following: a) All systems run an identical copy of HAD; b) HAD on each system maintains the state of its own resources, and sends all cluster information about the local system to all other machines in the cluster; c) HAD on each system receives information from the other cluster systems to update its own view of the cluster; and d) Each system follows the same code path for actions on the cluster.
In these classical distributed programming models, a programmer specifies computational resources, data structures, and their relationships a priori or constructs them during the initial phase of program execution. Hence the expression of such resources, data structures and relationships lies within the program. The challenge such systems face is maintaining integrity and structure of these relationships through failure and reconfiguration of the communication paths between the computational resources as the program executes. If this could be done simply and reliably (from the perspective of a programmer or system administrator), this would provide a rich characterization of connectedness, where previously TRUE and FALSE were the only assignable values for the property “connected” in conventional link-state management. This would enable more diverse responses by an agent, beyond a simple timeout and a specified number of retries.
Quantum Mechanics.
Quantum Mechanics (QM) describes the relationship between probabilities, information and observables. Put simply, QM may be regarded as the generalization of probability theory, which deals exclusively in positive numbers, to the domain of probability amplitudes which may take on positive, negative or complex values.
A classical computer stores bits (two-state symbols) such as 0 or 1. A quantum system stores qubits, representing, for example, photon polarization ↑ or ↓, AND any superposition (linear combination) of those two states (α↑+β↓), where the coefficients α and β represent the probability (over a series of measurements) of detecting the photon in that state.
Matrices are the mathematical language of quantum systems. The state |0> is equivalent to a column vector (e.g. 1 at the top, 0 at the bottom) and |1> represents another column vector (this time with 0 at the top and 1 at the bottom). This is the well-known Dirac Bra-ket formalism for a complex vector. In this formalism, <0| represents a row vector, with 1 on the left, and 0 on the right. <1| represents another row vector, this time with 0 on the left and 1 on the right. Since matrix mechanics involves the multiplication of a row vector by a column vector, this may be represented, for example, by <0|1> for the standard inner product, and |0><1| for the standard outer product. Multiplying out the standard inner product yields a number, 0, in the above example. Multiplying the standard outer-product yields a 2×2 matrix, (0,1;0,0) in the above example.
There are a number of 2×2 matrix operations with interesting properties, for example:
A Hadamard matrix (1,1;1,−1) is its own Inverse. e.g. H H*=I (the identity matrix) (1,0;0,1).
The bit flip operation is (0,1;1,0). //The phase flip operation is (1,0,0,−1).
Quantum operations are always unitary: quantum computations do not erase information or dissipate energy.
The publication “An insight into the nature of information, entanglement and time” predicted that: (a) time emerges from entanglement, and (b) that entanglement exists but quantum computing may be an illusion.
Experimental verification that time emerges from quantum entanglement has since been published and benchmarks of the D-Wave Machine appear to show no evidence of quantum speedup. While these results may be far from conclusive from a scientific perspective, if this insight turns out to be even partly correct, it opens up the potential for a revolution in the computer industry by transforming the way we incorporate the concept of time in the design of hardware, software, networks and information storage, and the algorithms that govern their reliability, performance and consistency of distributed data as our systems scale.